﻿#pragma once

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<time.h>

typedef int Datatype;

//设计堆的数据结构：堆是完全二叉树，采用数组实现
typedef struct Heap
{
	Datatype* a;  //数组的首元素地址
	int size;     //目前最后一个存入堆的元素（即存入数组尾部）的下标+1，存入堆的元素个数为size
	int capacity; //数组（堆）的长度
}Hp;

//函数设计：给定一个需要排序的数组，将数据传入堆的数组中进行排序
void HpInit(Hp* hp,Datatype* b,int n);  //对使用传入的数组首元素地址和数组长度对堆进行初始化
void HpInitUP(Hp* hp, Datatype* f, int Datasize);  //在原地向上建堆初始化
void HpPush(Hp* hp, Datatype c);  //把数据c加入到堆
void HpPop(Hp* hp);  //把根元素从堆中删除
void AddHpUp(Datatype* a, int size, int child);  //向上调整函数：a为传入数组首元素，size为数组目前大小，child为需要向上调整的数据的下标
void DelHpDown(Datatype* a, int size, int parent);  //向下调整函数：a为传入数组首元素，size为数组目前大小，parent为需要向下调整的数据的下标
void HpPrintf(Datatype*a,int size);  //打印堆中的所有数据

//对以上函数设计进行优化，对给定的数组进行原地排序
void HpSort(Datatype* a, int size);  //使用堆对传入的数组a进行原地建堆排序
void HpDInit(Hp* hp, Datatype* f, int Datasize);  //在原地建堆初始化

//TopK问题：当数据量巨大，且无法在内存中一次性存储，需要存在硬件的文件里，要找出该数据中前k个数时
void HPInitDown(Datatype* z, int zsize);  //原地向下建堆（传入的数组已经有了数据）
void CreateData();  //创建一个文件并且随即生成十万以内的5000个数字
void TopK();     //建堆找出的前k个数字并输出